1. Field of the Invention
The present invention relates to a network system having a router using an associative memory and, in particular, to an associative memory having a mask function.
2. Descrirtion of the Prior Art
The function that calculates the optimum transfer route is indispensable to a conventional network router (hereinafter simply called a router) in a computer network system, as follows.
Referring to FIG. 18, a conventional computer network will be described. A user or subscriber of the network has a user's terminal, such as a computer terminal, for connection to the network. A user's terminal is assigned with a specific network address in accordance with a predetermined rule when it is connected to the network in order to be distinguished from other user's terminals. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through fourth digits (a, b, c, d). The predetermined rule defines a hierarchical structure of the network address. The predetermined rule defines a hierarchical structure of the network address. For example, the first digit of the numeral represents a nation, such as England, Germany, and Japan. The second digit of the numeral represents a city in the nation, and the third digit of the numeral represents a company name in the city. In the following description, these hierarchical items will be called segments. Referring to FIG. 18, each segment is depicted by a rectangular block. Specifically, the network includes a first segment (SEGMENT1), second segment (SEGMENT2), and a third segment (SEGMENT3) at a highest hierarchical level. The first segment (SEGMENT1) and the second segment (SEGMENT2) include a fourth segment (SEGMENT4) and fifth segment (SEGMENT5), respectively. The fourth segment (SEGMENT4) and the fifth segment (SEGMENT5) include a sixth segment (SEGMENT6) and a seventh segment (SEGMENT7), respectively. A user's terminal (PC) 401-1 exists in the sixth segment. The first segment has a network address (1, *, *, *) in which a first digit alone is specified as “1”. The fourth segment subordinate to the first segment has a network address (1, 2, *. *) in which first and second digits “1” and “2” are specified. The sixth segment subordinate to the fourth segment has network address (1, 2, 2, *) in which first through third digits “1”, “2”, and “2” are specified. Thus, the user's terminal 401-1 in the sixth segment has a specific or unique network address (1, 2, 2, 1). The second segment has a network address (2, *, *, *) in which a first digit alone is specified as “2”. The fifth segment subordinate to the second segment has a network address (2, 1, *, *) in which first and second digits “2” and “1” are specified. The seventh segment subordinate to the fifth segment has network address (2, 1, 1, *) in which first through third digits “2”, “1”, and “1” are specified. A symbol “*” contained in these addresses represents “don't care”.
In order to connect or establish communication between a plurality of user's terminals in the network, each segment is provided with a router. As illustrated in FIG. 18, the first segment is provided with the first router 400-1, the second segment is provided with the second router 400-2, the third segment is provided with the third router 400-3, the forth segment is provided with the forth router 400-4, the fifth segment is provided with the fifth router 400-5, the sixth segment is provided with the sixth router 400-6, and the seventh segment is provided with the seventh router 400-7. Each router in the corresponding segment is supplied from any user's terminals or any routers connected to the router with transfer data and a transfer address annexed thereto. With reference to the transfer address and the relationship of connection of network apparatuses, the router calculates an optimum transfer route and transfers the transfer data via the optimum transfer route thus calculated. As illustrated in FIG. 18, each router is connected to any user's terminals or any routers subordinate to the corresponding segment. In addition, the third router 400-3 is connected to the router 400-1, the router 400-4, the router 400-6, the router 400-2, and router 400-7.
The user's terminals are not directly connected by the use of the communication channels but carry out communication by controlling the transfer of communication data by the use of communication control functions of the routers. Thus, communication channels as limited resources are saved.
Next referring to FIG. 19, the third router 400-3 will be described by way of example. Other routers have a similar structure.
The third router 400-3 memorizes, as network address information or data, the network addresses for the segments except the third segment to which the third router 400-3 belongs. Each digit of each network address is represented by a binary number of two bits. Thus, each network address is represented by a bit sequence of eight bits in total. For example, a network address (1, *, *, *) is represented by a bit sequence (01, 00, 00, 00). Hear after, a bit sequence represented above-mentioned representation is called a storage data. Since the symbol “*” represents “don't care” for each of second through fourth digits, it is necessary to indicate that the first and the second bits (01) in the bit sequence (01, 00, 00, 00) alone are valid and the remaining bits (00, 00, 00) are invalid. For this purpose, mask information (or mask data) is combined with the storage data or data. In the illustrated example, the mask information (or mask data) is given by a bit sequence (00, 11, 11, 11). Herein, “0” and “1” represent a mask invalid state and a mask valid state, respectively. In the third router 400-3, the storage data or data and the mask information or data are stored in an associative memory 116, as illustrated in FIG. 19. The first associative memory word 117-1 stores the network address (1, *, *, *) for the segment 1 to which the router 400-1 belongs. The second associative memory word 117-2 stores the network address (2, *, *, *) for the segment 2 to which the router 400-2 belongs. The third associative memory word 117-3 stores the network address (1, 2, 2, *) for the segment 6 to which the router 400-6 belongs. The fourth associative memory word 117-4 stores the network address (1, 2, *, *) for the segment 4 to which the router 400-4 belongs. The fifth associative memory word 117-5 stores the network address (2, 1, 1, *) for the segment 7 to which the router 400-7 belongs. The associative memory 116 has searching (or retrieving) function or mask searching function in addition to write/read functions of writing and reading storage data (namely, the address data) at a designated memory address in the matter similar to an ordinary memory circuit. Specifically, The associative memory 116 has the mask searching function to put the only mask match line 119 corresponding to the storage data with the least number of bits in a mask valid state, in the mask match lines 119 corresponding to one of the storage data coincident with the search data 102 taking the mask information into account, into a valid state, The encoder 402 encodes the mask match lines 119-1 through 119-5 that the associative memory 116 supplies into a memory address signal 403.
The memory 404 stores network addresses of the routers 400 corresponding to the segment network addresses each of which comprises the storage data and the mask information and each of which is stored in each associative memory word 117 of the associative memory 116. In the memory 404, each router network address is memorized in a word corresponding to the associative memory word 117 of the associative memory 116 where a corresponding network address is memorized. For example, the network address (1, *, *, *) is stored in the first associative memory word 117-1 of the associative memory 116 while the router network address of the router 400-1 (FIG. 18) corresponding thereto is stored in the first word of the memory 404. Similarly, the network address of the router 400-2, the network address of the router 400-6, the network address of the router 400-4, and the network address of the router 400-7 are stored in the second word, the third word, the fourth word, and fifth word of the memory 404, respectively. Supplied with the memory address signal 403 as a read address, the memory 404 produces a memory data signal 405 stored in the word designated by the memory address signal 403.
A cooling apparatus 414 cools the conventional associative memory 116 with large generation of heat. The cooling apparatus 414 can consist of for example, an air-cooling fan.
Although not illustrated in the figure, each router has a CPU for controlling the above-mentioned operation of the router.
Next, description will be made about a sending data operation in the conventional network controlled by the routers. It is assumed here that the transfer data supplied to the router 400-3 have a destination network address (1, 2, 1, 1). As a result of search by the associative memory 116, (1, *, *, *) in the first associative memory word 117-1 and (1, 2, *, *) in the fourth associative memory word 117-4 are coincident. Among those coincident network addresses, the network address (1, 2, *, *) in the fourth associative memory word 117-4 has the least number of bits in a mask valid state so that only the mask match line 119-4 corresponding to the fourth associative memory word 117-4 is put into a valid state. Therefore, the encoder 402 produces “4” as the memory address signal 403. In response to the memory address signal 403, the memory 404 produces as the memory data signal 405 the network address for the router 400-4. Consequently, the router 400-3 transfers the input transfer data having the destination network address (1, 2, 1, 1) to the router 300-4. The router 300-4 is responsive to the transfer data and performs the operation similar to that mentioned above. Thus, the transfer data are successively transferred from router to router until the user's terminal at the destination network address (1, 2, 1, 1) is reached.
Herein, referring to FIG. 14, a typical conventional associative memory will be described. As disclosed in Japanese Unexamined Patent Publication (JA-A) No. 11-073782 (073782/1999) an associative memory 116 comprises a two-input/one-output n-bit selector 128, first through m-th n-bit associative memory words 117, an n-bit latch 21, and a controller 131. Each associative memory word 117-j (where j is and integer variable between 1 and m, both inclusive) comprises first through n-th associative memory cells 118-j-1 through 118-j-n and a latch 123-j. Each of the associative memory words 117-j is connected to the corresponding data word line 106-j and the corresponding mask word line 111-j as input lines and to the corresponding mask match line 119-j and the first through the n-th shortest mask lines 122 as output lines and to the first through the n-th bit lines 103 as data input/output lines.
Each of the associative memory cells 118-j-k (where k is and integer variable between 1 and n, both inclusive) is connected to the corresponding data word line 106-j and the corresponding mask word line 111-j as input lines, and to the corresponding data match line 107-j, the corresponding mask match line 119-j, and the corresponding shortest mask line 122-k as output lines, and to the corresponding bit line 103-k as data input/output line.
Each associative memory cell 118-j-k comprises a data cell 108-j-k, a comparator 113-j-k, a mask cell 112-j-k, a mask comparator 120-j-k, and logical gate 121-j-k. The data cell 108-j-k is for storing “data” bit information at a corresponding bit of storage data supplied from an external source through a bit line 103-k. The comparator 113-j-k is for comparing the “data” bit information memorized in the data cell 108-j-k and “search” bit information 102-k at a corresponding bit of search data supplied from the external source. The mask cell 112-j-k is for storing “mask” bit information of a corresponding bit of mask information supplied from the external source through the bit line 103-k. The mask comparator 120-j-k is for comparing the “mask” bit information memorized in the mask cell 112-j-k and “shortest mask” bit information 127-k at a corresponding bit of shortest mask information produced from the n-bit latch 126.
In this example, a valid state and an invalid state are represented by “1” and “0”, respectively, for all of the mask information, the shortest mask lines 122-1 through 122-n, the data match lines 107-1 through 107-m, and the mask match lines 119-1 through 119-m.
The data cell 108 stores as the storage data the state on a corresponding bit line 103 on which the write data is driven when a corresponding data word line 106 is in a valid state, or supplies the storage data stored therein to the corresponding bit line 103 on which the write data is not driven when a corresponding data word line 106 is in a valid state. When the corresponding data word line 106 is in an invalid state, no operation is performed for the corresponding bit line 103. Irrespective of the state of the corresponding data word line 102, the storage data stored therein is supplied to the comparator 113 in the same associative memory cell 118.
The mask cell 112 stores as the mask information the state on a corresponding bit line 103 on which the write data is driven when a corresponding mask word line 111 is in a valid state, or supplies the mask information stored therein to the corresponding bit line 103 on which the write data is not driven when a corresponding mask word line 111 is in a valid state. When the corresponding mask word line 111 is in an invalid state, no operation is performed for the corresponding bit line 103. Irrespective of the state of the corresponding mask word line 111, the mask information stored therein is supplied to the comparator 113 in the same associative memory cell 118.
Prior to the start of the searching operation, the data match line 107 is precharged to a high level or pulled up by a resistor (not shown) to be put into a valid state “1”.
The comparator 113 is supplied with the value of the search data on the corresponding bit line 103, the storage data stored in the data cell 108 in the same associative memory cell 118, and the mask information stored in the mask cell 110 in the same associative memory cell 118. When the mask information is in a valid state or when the value on the corresponding bit line 103 and the storage data stored in the data cell 108 are coincident with each other, the data match line 107 is put into an opened state. Otherwise, the comparator 113 puts the data match line 107 into an invalid state “0”. Thus, the wired AND logic connection is achieved such that, when all of the comparator 113, n in number, in the associative memory word 117 render the data match line 107 in an opened state, the data match line 107 is put into a valid state “1” and otherwise into an invalid state “0”. In other words, upon the searching operation, only when all of the storage data stored in an associative memory word 117 is completely coincident with the bit lines 103-1 through 103-n except those bits excluded from a comparison object by the corresponding mask information, the data match line 107 is put into a valid state “1” and otherwise into an invalid state “0”. Alternatively, an ordinary logical gate may be used as far as the similar operation is performed.
The logical gate 121 supplies an invalid state “0” to the shortest mask line 122 when the data match line 107 in the same associative memory word 117 is in a valid state “1” and the mask information stored in the corresponding mask cell 112 is in an invalid state “0”. Otherwise, the logical gate 121 puts the shortest mask line 122 into an opened state.
Each of the shortest mask line 122-1 through 122-n is pulled up by a corresponding register 125 to be put into a valid state “1”. The shortest mask line 122-k (where k is and integer variable between 1 and n, both inclusive) is connected to all of the corresponding logical gates 121-1-k through 121-m-k, m in number, by a wired AND logic connection. Thus, when all of the first though m-th logical gates 121 connected to the corresponding shortest mask line 122 render the shortest mask line 122 in an opened state, the shortest mask line 122 is put into a valid state “1” and otherwise into an invalid state “0”.
The latches 123-1 though 123-m store the states of the data match lines 107-1 through 107-m in the associative memory words 117-1 through 118-m as stored states, respectively, when latch control signal 124 is in valid state. In order to produce the stored states, each latch 123 is connected to the mask match line 119 in the same associative memory word 117 by the wired logic connection. The latches 123-1 through 123-m supply to the corresponding mask match lines 119-1 through 119-m with an invalid state “0” when the stored data have an invalid state “0”, respectively, and put the corresponding mask match lines 119-1 through 119-m into an opened state when the stored data have a valid state “1”.
Upon completion of the searching operation, only one of the mask match lines 119-1 through 119-m is put into a valid state while the others are put into an invalid state. The mask match line 119 put into a valid state corresponding to one of the storage data coincident with the search data 102 which has the least number of bits excluded from the search object by the mask information. Each of the mask match lines 119-1 through 119-m are pulled up by a resistor (not shown) prior to start of the searching operation or precharged to a high level to be put into a valid state “1”.
Each of the mask comparator 120 compares the state of the mask information stored in the corresponding mask cell 112 and the shortest mask information on the corresponding bit line 103. Upon coincidence, the mask comparator 120 puts the corresponding mask match line 119 into an opened state. Upon incoincidence, the mask comparator 120 supplies an invalid state “0” to the corresponding mask match line 119. Thus, the wired AND logic connection is achieved such that, when all of the associative memory cells 118, n in number, and the latch 123 in the same associative memory word 117 render the mask match line 119 in an opened state, the mask match line 119 is put into a valid state “1” and otherwise into an invalid state “0”.
In other words, upon the searching operation, only when the mask information stored in the associative memory word 117 is completely coincident with the bit lines 103-1 through 103-n and the state of the data match line 107 stored in the latch 123 is a valid state “1”, the mask match line 119 is put into a valid state “1” and otherwise into an invalid state “0”.
The n-bit latch 126 stores the states of the shortest mask lines 122-1 through 122-n as stored states when a latch control signal 124 is in a valid state. The n-bit latch 126 supplies the stored states to the latch output lines 127-1 through 127-n.
With reference to the state of a selection signal 129, the two-input/one-output n-bit selector 128 selects, as output data to be supplied to the bit lines 103-1 through 103-n, either the search data 102-1 through 102-n or latch output lines 127-1 through 127-n.
The controller 131 supplies a latch control signal 124 and a selection signal 129 synchronizing with a clock signal 130, in order to control operation of the associative memory 116.
Next referring to FIG. 15, the associative memory cell 118 will be described. Two bit lines 103a and 103b correspond to each bit line 103 illustrated in FIG. 14. In FIG. 14, each single bit line 103-i collectively represents these bit lines 103a and 103b. Through the two bit lines 103a and 103b, writing and reading of the data into and from the memory cell and the input of the search data 102 are carried out. Upon writing the data or the input of the search data 102, the bit line 103b is supplied with an inverted value of a value on the bit line 103a. The data cell 108 is a typical SRAM (Static Random Access Memory) comprising inverted logical gates (G101 and G102) 301 and 302 with one's input and output terminals connected to the other's output and input terminals, respectively, a MOS (Metal Oxide Semiconductor) transistor (T101) 303 connecting the output terminal of the inverted logical gate (G102) 302 to the bit line 103a and rendered conductive when the data word line 106 has a high level, and a MOS transistor (T102) 304 connecting the output terminal of the inverted logical gate (G101) 301 to the bit line 103b and rendered conductive when the data word line 106 has the high level.
The mask cell 112 is also a typical SRAM comprising inverted logical gates (G103 and G104) 309 and 310 with one's input and output terminals connected to the other's output and input terminals, respectively, a MOS transistor (T107) 311 connecting the output terminal of the inverted logical gate (G104) 310 to the bit line 103a and rendered conductive when the mask word line 111 has ha high level, and a MOS transistor (T108) 312 connecting the output terminal of the inverted logical gate (G103) 309 to the bit line 103b and rendered conductive when the mask word line 111 has the high level.
The comparator 113 comprises a MOS transistor (T103) 305, a MOS transistor (T104) 306, a MOS transistor (T105) 307, and a MOS transistor (T106) 308. The MOS transistor (T103) 305 and the MOS transistor (T104) 306 are inserted between the bit lines 103a and 103b in cascade. The MOS transistor (T103) 305 is rendered conductive when the inverted logical gate (G101) 301 in the data cell 108 produces an output of a high level. The MOS transistor (T104) 306 is rendered conductive when the inverted logical gate (G102) 302 in the data cell 108 produces an output of a high level. The MOS transistor (T105) 307 and the MOS transistor (T106) 308 are connected between a low potential and the data match line 107 in cascade. The MOS transistor (T105) 307 is rendered conductive when a junction or node of the MOS transistor (T103) 305 and the MOS transistor (T104) 306 has a potential of a high level. The MOS transistor (T106) 308 is rendered conductive when the inverted logical gate (G103) 309 in the mask cell 112 produces an output of a high level. When both the bit line 103a and the inverted logical gate (G101) 301 produce outputs of a high level or when both the bit line 103b and the inverted logical gate (G102) 302 produce outputs of a high level, the junction of the MOS transistor (T103) 305 and the MOS transistor (T104) 306 has a high level to render the MOS transistor (T105) 307 conductive.
Therefore, when the storage data stored in the data cell 108 and the search data 102 on the bit lines 103a and 103b are different from each other, the MOS transistor (T105) 307 is rendered conductive. The MOS transistor (T106) 308 is put into an opened state and conductive state when the mask information stored in the mask cell 112 is “1” and “0”, respectively. The data match line 107 is pulled up to a high potential by the resistor (not shown) or precharged to a high potential prior to the start of the searching operation. This provides the wired AND connection such that, when a plurality of the associative memory cells 118 are connected to the data match line 107 through the MOS transistors (T106) 308, the data match line 107 is given a low level if at least one associative memory cell 118 produces an output of a low level.
When both the MOS transistor (T105) 307 and the MOS transistor (T106) 308 are conductive, the associative memory cell 118 supplied an invalid state “0” to the data match line 107. Otherwise, the data match line 107 is put into an opened state. Specifically, when the mask information is “1”, the data match line 107 is put into an opened state. When the mask information is “0”, the data match line 107 is put into an opened state and supplied with an invalid state “0” when the search data 102 on the bit lines 103a and 103b and the storage data stored in the data cell 108 are coincident with each other and different from each other, respectively.
Next, the logical gate 121 and the shortest mask line 122 will be described. The shortest mask line 122 is pulled up by a register 125 (FIG. 14) to be put into a valid state “1” prior to a searching operation. The logical gate 121 comprises MOS transistors (T109 and T110) 313 and 314 connected in cascade between the shortest mask line 122 and a low potential. The MOS transistor (T109) 313 is put into a conductive state and an opened state when a data match line 107 is in a valid state “1” and an invalid state “0”, respectively. The MOS transistor (T110) 314 is put into a conductive state and an opened state when an inverted logical gate (G103) 309 in the mask cell 112 produces an output of a high level and a low level, respectively, i.e., when the mask information stored in the mask cell 112 is in an invalid state “0” and a valid state “1”, respectively. Thus, the logical gate 121 supplies an invalid state “0” to the shortest mask line 122 when the data match line 107 is in a valid state “1” and the mask information stored in the mask cell 112 is in an invalid state “0”. Otherwise, the logical gate 121 puts the shortest mask line 122 into an opened state.
Next, description will proceed to the operation of the mask comparator 120 and the mask match line 119. The mask match line 119 is pulled up to a high potential by a resistor (not shown) or precharged to a high potential prior to the searching operation.
The mask comparator 120 comprises MOS transistors (T111, T112, and T113) 315, 316, and 317. The MOS transistors (T111 and T112) 315 and 316 are connected in cascade between the bit lines 103a and 103b. The MOS transistor (T111) 315 is put into a conductive state when the inverted logical gate (G103) 309 in the mask cell 112 produces an output of a high level. The MOS transistor (T112) 316 is put into a conductive state when an inverted logical gate (G104) 310 in the mask cell 112 produces an output of a high level. The MOS transistor (T113) 317 is connected between a low potential and the mask match line 119. The MOS transistor (T113) 317 is put into a conductive state when a junction or node of the MOS transistor (T111) 315 and the MOS transistor (T112) 316 has a potential of a high level.
When both the bit line 103a and the inverted logical gate (G103) 309 produce outputs of a high level or when both the bit line 103b and the inverted logical gate (G104) 310 produce outputs of a high level, the junction of the MOS transistor (T111) 315 and the MOS transistor (T112) 316 has a potential of a high level so that the MOS transistor (T113) 317 is put into a conductive state. Otherwise, the MOS transistor (T113) 317 is put into an opened state.
Therefore, when the mask information stored in the mask cell 112 is different form the search data 102 on the bit lines 103a and 103b, the MOS transistor (T113) 317 is put into a conductive state to supply an invalid state “0” to the mask match line 119. Upon coincidence, the mask match line 119 is put into an opened state.
Thus, a wired AND connection is achieved such that, when at least one of the associative memory cells 118 connected through the MOS transistor (T113) 317 to the mask match line 119 produces a low level, the mask match line 119 is given a low level and otherwise a high level.
Next referring to FIG. 16, description will be made about the operation when the above-mentioned conventional associative memory 116 is used in calculating the transfer network address in the router 400-3 in FIG. 18. Referring to FIG. 17, this operation will be described by the use of a timing chart.
It is assumed here that the associative memory 116 comprises five words of eight bits. Therefore, the storage data and the mask information stored in each of the associative memory words 117-1 through 117-5 are quite similar to those of the associative memory 116 in FIG. 19. The associative memory 116 memorizes the connection information except the network address (3, *, *, *) of the router 400-3 in FIG. 18. Specifically, the associative memory word 117-1 stores in binary numbers the storage data (01, 00, 00, 00) and the mask information (00, 11, 11, 11) to implement (1, *, *, *). Likewise, the associative memory words 117-2, 117-3, 117-4, and 117-5 stores (2, *, *, *), (1, 2, 2, *), (1, 2, *, *), and (2, 1, 1, *), respectively. Description will proceed to the searching operation by supplying as the search data 102 the network address (1, 2, 2, 1), in quadridecimal numbers, of the user's terminal (PC) 401-1 in FIG. 18.
At first, all of the data match lines 107-1 through 107-8 are precharged to a high level (“1”) to be put into a valid state “1” at the timing (1) in FIG. 17.
Next, the two-input/one-output 8-bit selector 128 is responsive to the selection signal 129 which the controller 131 supplies, and selects the search data 102 to deliver the search data 102 to the bit lines 103-1 through 103-8 at the timing (2) in FIG. 17. Therefore, the quadridecimal notations (1, *, *, *), (1, 2, 2, *) and (1, 2, *, *) respectively stored in the associative memory words 117-1, 117-3 and 117-4 in the associative memory 116 are coincident with the search data 102 on the bit lines 103. Accordingly, the data match lines 107-1, 107-3 and 107-4 are put into a valid state “1” while the remaining data match lines 107-2, and 107-5 are put into an invalid state “0”.
Herein, the shortest mask line 122-1 produces the logical product “0” of the mask bit information “0”, “0” and “0” in the associative memory words 117-1, 117-3 and 117-4 at bit positions corresponding to the shortest mask line 122-1. The shortest mask line 122-2 produces the logical product “0” of the mask information “0”, “0” and “0” in the associative memory words 117-1, 117-3 and 117-4 at bit positions corresponding to the shortest mask line 122-2. Likewise, the shortest mask lines 122-3, 122-4, 122-5, 122-6, 122-7, and 122-8 produce the logical product “0” of “1”, “0” and “0”, the logical product “0” of “1”, “0” and “0”, the logical product “0” of “1”, “0” and “1”, the logical product “0” of “1”, “0” and “1”, the logical product “1” of “1”, “1” and “1”, and the logical product “1” of “1”, “1” and “1”, respectively. As a result, the binary notation “00000011” is delivered to the shortest mask lines 122-1 through 122-8.
In this state, the latch control signal 124 that the controller 131 supplies is put into valid state. The latches 123-1 through 123-5 store the states of the corresponding match lines 107-1 through 107-5, respectively, while the n-bit latch 126 stores the states of the shortest mask lines 122-1 through 122-8. Accordingly, the latches 123-1, 123-2, 123-3, 123-4, and 123-5 store “1”, “0”, “1”, “1”, and “0”, respectively, while the n-bit latch 126 stores the binary notation “00000011”. The n-bit latch 126 delivers the stored state “00000011” to the latch output line 127-1 through 127-8.
Next, at the timing (3) in FIG. 17, all of the mask match lines 119-1 through 119-8 are precharged to a high level to be put into a valid state “1”.
At the timing (4) in FIG. 17, in response to the selection signal 129 which the controller 131 supplies, the two-input/one-output 8-bit selector 128 selects the latch output line 127 and supplies the information “00000011” on the latch output line 127 to the corresponding bit lines 103-1 through 103-8. Thereafter, the associative memory 116 starts a second searching operation. In the second searching operation, use is made of the states of the mask match lines 119-1 through 119-8 while the states of the data match line 107-1 through 107-8 are ignored.
The mask information stored in each of the associative memory words 117-3 and 117-5 is completely coincident with the states “00000011” on the bit lines 103-1 through 103-8 so that the corresponding mask match lines 119-3 and 119-5 are put into an opened state. Since the mask information stored in any other associative memory words 117-1, 117-2, and 117-4 is not coincident, the corresponding mask match lines 119-1, 119-2, and 119-4 are supplied with an invalid state “0”.
The latch 123-1 puts the corresponding mask match line 119-1 into an opened state because the stored state is “1”. The latch 123-2 delivers the stored state “0” to the corresponding mask match line 119-2. The latch 123-3 puts the corresponding mask match line 119-3 into an opened state because the stored state is “1”. The latch 123-4 puts the corresponding mask match line 119-4 into an opened state because the stored state is “1”. The latch 123-5 delivers the stored state “0” to the corresponding mask match line 119-5.
Therefore, the mask match line 119-1 is put into an invalid state “0” because the mask comparators 120-1-1 through 120-1-8 of the associative memory word 117-1 produce “0” although the latch 123-1 is in an opened state. The mask match line 119-2 is put into an invalid state “0” because the mask comparators 120-2-1 through 120-2-8 of the associative memory word 117-2 produce “0” and the latch 123-2 produces “0”. The mask match line 119-3 maintains a valid state “1” because the mask comparators 120-3-1 through 120-3-8 of the associative memory word 117-3 are in an opened state and the latch 123-3 is in an opened state. The mask match line 119-4 is put into an invalid state “0” because the mask comparators 120-4-1 through 120-4-8 of the associative memory word 117-4 produce “0” although the latch 123-4 is in an opened state. The mask match line 119-5 is put into an invalid state “0” because the mask comparators 120-5-1 through 120-5-8 of the associative memory word 117-5 are in an opened state although the latch 123-5 produces “0”.
Consequently, only one of the mask match line 119-1 through 119-5 corresponding to a particular one the associative memory words 117-1 through 117-5 is in a valid state “1” upon completion of the second searching operation at the timing (4). Specifically, the storage data preliminarily stored in the particular associative memory word (117-3 in the illustrated example) is selected in the first search operation as coincident with the search data 102 taking the mask information into account while the mask information preliminarily stored is selected in the second searching operation as coincident with the states of the shortest mask lines 122-1 through 122-8 obtained by the first searching operation at the timing (2). It will therefore be understood that, in the mask match lines 119 corresponding to one of the storage data coincident with the search data 12 taking the mask information into account, the only mask match line 119-3 corresponding to the storage data with the least number of bits in a mask valid state is put into a valid state
As described above, the associative memory 116 supplies the comparison result of the search data 102 and the storage data stored in the first through m-th associative memory words 117 to the first through the data match lines 107 upon the first searching operation, and supplies the comparison result of the value on the latch output line 127 and the mask information stored in the first through m-th associative memory words 117 to the first through the match lines 107 upon the second searching operation. For this purpose, the associative memory cell 118, n in number, in the each of the first through m-th associative memory word 117 the requires two kinds of comparing means, comparators 113 comparing the storage data and mask comparators 120 comparing the mask information.
Herein, when it is assumed that each of the inverted logical gates comprises two MOS transistors, the associative memory cell 118 comprises 18 MOS transistors as readily understood from FIG. 15. Since both the data cell 108 and the mask cell 112 are typical SRAMs, the circuit area of each transistor comprising these is similar to the circuit area of the minimum MOS transistor, in general.
However, each of the data match lines 107-1 through 107-m is connected to the first through n-th comparator 113 in the corresponding associative memory word 117 by a wired AND logic connection so that the data match line 107 requires enough length to achieve this connection. Thus, the parasitic capacitance of each of the data match lines 107-1 through 107-m is very large so that the MOS transistors that composes the comparator 10 and the logical gate 11 require large circuit area in order to drive the large parasitic capacitances of each of the data match lines 107. For example, in case of 0.25 micron meter rule manufacturing process, the wiring length is required about 1 millimeter in order to connect to 64 comparators, so that the parasitic capacitance of each data match line 107 is about 0.3 pF. Accordingly, the size of each transistor that drives above-mentioned capacitance requires about 10 to 30 times as large as the size of the minimum transistor for the manufacturing process. Likewise, each of the mask match lines 119-1 through 119-m is connected to the first through n-th mask comparator 120 by a wired AND logic connection so that the size of each transistor that composes the logical gate 121 requires about 10 to 30 times as large as the size of the minimum transistor for the manufacturing process. In the meanwhile, each of the shortest mask lines 122-1 through 122-n is connected to the first through m-th logical gates 121 by a wired AND logic connection so that the shortest mask lines 122 requires enough length to achieve this connection. Thus, the size of each transistor that composes the logical gate 121 requires about 10 to 30 times as large as the size of the minimum transistor for the manufacturing process.
Herein, it is assumed that the circuit area of each MOS transistor that composes the comparator 113, the mask comparator 120, and the logical gate 121 is 10 times as the circuit area of the minimum MOS transistor and the circuit area of a typical SRAM is 6 times as the circuit area of the minimum MOS transistor. Accordingly, as readily understood from FIG. 15, the circuit area of the associative memory cell 118 is 102 times as the circuit area of the minimum MOS transistor. In other words, the conventional associative memory 116 has only 1/17 of the storage capacity in comparison with a SRAM that has the same chip area.
As described above, the data match lines 107-1 through 107-m are supplied with the comparison result upon the first searching operation, and the mask match lines 119-1 through 119-m are supplied with the comparison result upon the second searching operation. Therefore, the conventional associative memory requires maintaining the comparison result of the first searching operation until the start of the second searching operation. Herein, if the associative memory 116 comprises the first through 32768th 64-bit associative memory words and the latch 123 comprises 10 MOS transistors, about 330,000 transistors are required in order to compose the latch 123, 32,768 in number. In other words, irrespective of number of bits of the storage data, the chip area of the conventional associative memory increases by a circuit area of the latch 123-1 through 123-m, m in number.
In the meanwhile, each of the data match lines 107-1 through 107-m, m in number, and the mask match lines 119-1 through 119-m, m in number, except one mask match line that is put into a valid state upon completion of the searching operation, discharge the charge that is precharged thereto through the corresponding MOS transistor for every searching operation. Therefore, if the associative memory comprises the first through 32768th 64-bit associative memory words, the parasitic capacitance corresponding to 65,535 lines requires being precharged, as given by 32,768×2−1=65,535. The parasitic capacitance of the shortest mask lines 122-1 through 122-n is negligible because the shortest mask lines 122-1 through 122-n are n in number. In other words, power consumption of the conventional associative memory mainly comprises the power that is consumed when the data match lines 107 and mask match lines 119 are precharged for every searching operation. Herein, it is assumed that each parasitic capacitance of the data match line 107 and mask match line 119 is 0.3 pF, and that the supplied voltage is 2.5V, and that the period of the clock signal 130 is 20 ns. Accordingly, as described above, in case of 0.25 micron meter rule manufacturing process, the power consumption of the whole chip is very large as given by (0.3 pF×2.5V)×2.5V/20 ns×65,535=6.1 W. Therefore, since each of the data match lines 107-1 through 107-m, m in number, and the mask match lines 119-1 through 119-m, m in number, except one mask match line that is put into a valid state upon completion of the searching operation, requires being precharged to be put into a valid state Prior to the start of every searching operation, the conventional associative memory has very large power consumption.
As described above, the conventional router requires a plurality of the associative memory 116 since the storage capacity of the associative memory 116 is small. Therefore the conventional router generates a large amount of heat so that the cooling apparatus 414 is requires as illustrated in FIG. 19. Further, the data transfer rate decreases since the conventional router requires comparing to the results of the searching operation supplied from a plurality of the associative memory in order to calculate the final result of the searching operation.